﻿namespace System.Collections.Generic
{
	public class FastValueArray<T> : ICloneable where T : struct
	{
		public const int DEFAULT_CAPACITY = 32;
		protected PoolComparer comparer;
		public bool Fix;
		protected T[] Pool;

		protected FastValueArray()
		{
			comparer = new PoolComparer();
		}

		public FastValueArray(int capacity)
		{
			comparer = new PoolComparer();

			if (capacity <= 0)
			{
				throw new InvalidOperationException(string.Format("ERROR: new FastValueArray create failed. capacity is = {0}", capacity));
			}

			Pool = new T[capacity];
		}

		public FastValueArray(int capacity, int count)
		{
			comparer = new PoolComparer();

			if (capacity <= 0)
			{
				throw new InvalidOperationException(string.Format("ERROR: new FastValueArray create failed. capacity is = {0}", capacity));
			}

			Pool = new T[capacity];
			Resize(count);
		}

		public void Add(T item)
		{
			int idx = Count;

			if (idx >= Capacity)
			{
				AllocateMore();
			}

			Pool[idx] = item;
			Count++;
		}

		public void AddAt(T item, int idx)
		{
			if (Count >= Capacity)
			{
				AllocateMore();
			}

			int index = Count - 1;
			while (index != idx - 1)
			{
				Pool[index + 1] = Pool[index];
				index--;
			}

			Pool[idx] = item;
			Count++;
		}

		public void AddAtRange(T[] items, int idx, int start, int count)
		{
			int index = start;

			while (index < start + count)
			{
				AddAt(items[index], idx);
				index++;
				idx++;
			}
		}

		public void AddRange(T[] items, int start, int count)
		{
			int index = start;

			while (index < start + count)
			{
				Add(items[index]);
				index++;
			}
		}

		protected void AllocateMore()
		{
			if (Fix)
			{
				throw new OverflowException(string.Format("ERROR: This is a fixed fast value array! FastArray.AllocateMore() failed. capacity = {Capacity}, count = {Count}", Capacity, Count));
			}

			int newCount = Count * 2;
			Reserve(newCount <= DEFAULT_CAPACITY ? DEFAULT_CAPACITY : newCount);
		}

		public int BinarySearch<T2>(T2 item, SearchComparison<T2> comparison)
		{
			return BinarySearch<T2>(0, Count, item, comparison);
		}

		public int BinarySearch<T2>(int startIdx, int count, T2 item, SearchComparison<T2> comparison)
		{
			if (count == 0)
			{
				return -1;
			}

			int tail = startIdx + count;
			int middle = startIdx + count / 2;
			int comp = comparison(Pool[middle], item);

			if (comp > 0)
			{
				return BinarySearch<T2>(middle + 1, tail - middle - 1, item, comparison);
			}

			if (comp < 0)
			{
				return BinarySearch<T2>(startIdx, middle - startIdx, item, comparison);
			}

			return middle;
		}

		public void Clear()
		{
			Resize(0);
		}

		public object Clone()
		{
			return FastValueArray<T>.Copy((FastValueArray<T>)this);
		}

		public bool Contains(T item)
		{
			return IndexOf(item) != -1;
		}

		public static FastValueArray<T> Copy(FastValueArray<T> src)
		{
			FastValueArray<T> array = new FastValueArray<T>(src.Capacity);
			int idx = 0;

			while (idx < src.Count)
			{
				array.Add(src[idx]);
				idx++;
			}

			return array;
		}

		public void CopyTo(int sourceIndex, T[] destination, int destinationIndex, int count)
		{
			if (destination.Length < destinationIndex + count)
			{
				throw new ArgumentOutOfRangeException(string.Format("ERROR: FastValueArray.CopyTo() failed. out of range(dst len = {0}, end idx = {1})", destination.Length, destinationIndex + count));
			}

			for (int i = 0; i < count; i++)
			{
				destination[destinationIndex + i] = Pool[sourceIndex + i];
			}
		}

		public void Fill(int idx, int count, Creator ctor)
		{
			if (idx + count > Count)
			{
				Count = idx + count;
			}

			for (int i = 0; i < count; i++)
			{
				Pool[idx] = ctor(idx);
				idx++;
			}
		}

		public int IndexOf(T item)
		{
			return IndexOf(item, 0, Count);
		}

		public int IndexOf(T item, int startIdx)
		{
			return IndexOf(item, startIdx, Count - startIdx);
		}

		public int IndexOf(T item, int startIdx, int count)
		{
			for (int i = startIdx; i < count; i++)
			{
				if (Pool[i].Equals(item))
				{
					return i;
				}
			}

			return -1;
		}

		public int LastIndexOf(T item)
		{
			return LastIndexOf(item, 0, Count);
		}

		public int LastIndexOf(T item, int startIdx)
		{
			return LastIndexOf(item, startIdx, Count - startIdx);
		}

		public int LastIndexOf(T item, int startIdx, int count)
		{
			int index = startIdx + count - 1;   // tail
			int head = startIdx - 1;            // start

			while (index != head)
			{
				if (Pool[index].Equals(item))
				{
					return index;
				}
				index--;
			}

			return -1;
		}

		public bool Remove(T item)
		{
			int index = IndexOf(item);
			if (index == -1)
			{
				return false;
			}

			RemoveAt(index);

			return true;
		}

		public void RemoveAt(int idx)
		{
			int index = idx + 1;

			while (index < Count)
			{
				Pool[index - 1] = Pool[index];
				index++;
			}

			Count--;
		}

		public void RemoveRange(int startIdx, int count)
		{
			if (startIdx < 0 || startIdx > Count)
			{
				throw new ArgumentOutOfRangeException(string.Format("ERROR: FastValueArray.RemoveRange() failed. start idx = {0}, count = {1}", startIdx, Count));
			}

			if (count != 0 && startIdx != Count)
			{
				if (count < 0 || startIdx + count > Count)
				{
					count = Count - startIdx;
				}

				int tail = startIdx + count;

				if (tail < Count)
				{
					// 把尾部的数据移动到前面
					int index = tail;
					while (index < Count)
					{
						Pool[index - count] = Pool[index];
						index++;
					}
				}

				Count -= count;
			}
		}

		public void Reserve(int reserveCount)
		{
			if (reserveCount > Capacity)
			{
				T[] destinationArray = new T[reserveCount];

				if (Count > 0)
				{
					Array.Copy(Pool, destinationArray, Count);
				}

				Pool = destinationArray;
			}
		}

		public void Resize(int count)
		{
			/// todo: 如果AllocateMore double后count依旧大于Capacity 怎么办...
			if (count > Capacity)
			{
				AllocateMore();
			}

			Count = count;
		}

		public void Reverse()
		{
			Reverse(0, Count);
		}

		public void Reverse(int startIdx, int count)
		{
			int tail = startIdx + count - 1;
			int mid = startIdx + count / 2;
			int index = startIdx;

			for (int i = 0; index < mid; i++)
			{
				T tmp = Pool[index];
				Pool[index] = Pool[tail - i];
				Pool[tail - i] = tmp;

				index++;
			}
		}

		public void Sort(Comparison<T> comparison)
		{
			Sort(0, Count, comparison);
		}

		public void Sort(int startIdx, int count, Comparison<T> comparison)
		{
			comparer.Comp = comparison;
			Array.Sort<T>(Pool, startIdx, count, comparer);
		}

		public T[] ToArray()
		{
			return Pool;
		}

		public int Capacity
		{
			get
			{
				return Pool.Length;
			}
		}

		public int Count { get; protected set; }

		public T this[int idx]
		{
			get
			{
				if (idx < 0 || idx >= Count)
				{
					throw new ArgumentOutOfRangeException(string.Format("ERROR: FastArray[idx] failed. idx = {0}, count = {1}", idx, Count));
				}

				return Pool[idx];
			}
			set
			{
				Pool[idx] = value;
			}
		}

		public delegate T Creator(int idx);

		protected class PoolComparer : IComparer<T>
		{
			public Comparison<T> Comp;

			public int Compare(T x, T y)
			{
				return Comp(x, y);
			}
		}

		public delegate int SearchComparison<T2>(T x, T2 y);
	}
}